package master;

/**
 * @author chenyw
 * @date 2022/8/21 11:30
 *
 ( 对链表进行插入排序
 *
 */
public class M147insertionSortList {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        ListNode cur = head.next;
        ListNode lastSortedNode = pre.next;
        while (cur != null) {
            if (lastSortedNode.val <= cur.val) {
                lastSortedNode = lastSortedNode.next;
            } else {
                pre = dummyNode;
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                //插入
                lastSortedNode.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = lastSortedNode.next;
        }
        return dummyNode.next;
    }
}
